package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author Fengkai
 * @creat 2023/4/17
 * 题目描述
 * 给定一个数组，我们称其中连续的元素为连续子序列，称这些元素的和为连续子序列的和。数组中可能存在几组连续子序列，组内的连续子序列互不相交且有相同的和。
 * 求一组连续子序列，组内子序列的数目最多。输出这个数目。
 * 输入描述:
 * 第一行输入为数组长度 N，1 <= N <= 10^3.
 * 第二行为 N 个用空格分开的整数 Ci，-10^5 <= Ci <= 10^5.
 * 输出描述:
 * 第一行是一个整数 M，表示满足要求的最多的组内子序列的数目。
 * 示例1
 * 输入:
 * 10
 * 8 8 9 1 9 6 3 9 1 0
 * 输出:
 * 4
 */
public class LianXuZiSumSize {
    public static void main (String[] args) {
        int[] nums = new int[]{8, 8, 9, 1, 9, 6, 3, 9, 1, 0};
        System.out.println(maxSubArray(nums));
    }

    public static int maxSubArray (int[] nums) {
        HashMap<Integer, Integer> countKey = new HashMap<>(); //key为子序列和，value为子序列数目
        HashMap<Integer, Integer> keyRight = new HashMap<>(); //key为子序列和，value为子序列最右元素
        int preSum[] = new int[nums.length + 1]; //每个元素位置到第一个元素的和
        int result = 0;
        for (int i = 0; i < preSum.length - 1; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
            for (int j = i; j >= 0; j--) {
                int target = preSum[i + 1] - preSum[j];
                if(keyRight.getOrDefault(target, 0) <= j){
                    keyRight.put(target, i+1);
                    countKey.put(target, countKey.getOrDefault(target, 0) + 1);
                    result = Math.max(result, countKey.get(target));
                }
            }
        }
        System.out.println(Arrays.toString(preSum));
        return result;
    }
}
